package LeetCode刷题.之前的算法;

public class samePoint {
    //第一个相同的公共节点---用双指针法搞定
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            //用set集合实现 但是耗内存
            //     Set<ListNode> set=new HashSet<>();
            //    while(headA!=null){
            //         set.add(headA);
            //         headA=headA.next;
            //    }
            //     while (headB!=null){
            //         if(set.contains(headB)){
            //             return headB;
            //         }
            //         headB=headB.next;
            //     }
            int len1 = length(headA);
            int len2 = length(headB);
            // System.out.println(len1+" "+len2);
            while (len1 != len2) {
                if (len1 > len2) {
                    len1--;
                    headA = headA.next;
                } else {
                    len2--;
                    headB = headB.next;
                }
            }
            while (headA != headB) {
                headA = headA.next;
                headB = headB.next;
            }
            return headA;
        }

        public int length(ListNode head) {
            int len = 0;
            while (head != null) {
                len++;
                head = head.next;
            }
            return len;
        }
    }
}
